package com.mapbar.ure.frontend.lr1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.mapbar.ure.ASTException;
import com.mapbar.ure.ProductionType;
import com.mapbar.ure.backend.DFA;
import com.mapbar.ure.backend.NFA;
import com.mapbar.ure.backend.converter.NFA2DFAConverter;
import com.mapbar.ure.backend.converter.REAST2NFAConverter;
import com.mapbar.ure.frontend.lr1.table.Action;
import com.mapbar.ure.frontend.lr1.table.ActionType;
import com.mapbar.ure.frontend.lr1.table.Goto;
import com.mapbar.ure.frontend.parser.AST;
import com.mapbar.ure.frontend.parser.Parser;

/**
 * 语法结构，根据语法生成LR1表格，用于parser的解析。
 * 
 * @author qin
 * 
 */
public class Grammar {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Grammar g = new Grammar();

		// 括号语法
		g.addProduction(new Production(ProductionType.Goal,
				new ProductionType[][] { { ProductionType.List } }));
		g.addProduction(new Production(ProductionType.List,
				new ProductionType[][] {
						{ ProductionType.List, ProductionType.Pair },
						{ ProductionType.Pair } }));
		g.addProduction(new Production(ProductionType.Pair,
				new ProductionType[][] {
						{ ProductionType.OpeningParenthesis,
								ProductionType.Pair,
								ProductionType.ClosingParenthesis },
						{ ProductionType.OpeningParenthesis,
								ProductionType.ClosingParenthesis } }));

		// RE语法
		g = new Grammar();
		g.addProduction(new Production(ProductionType.Goal,
				new ProductionType[][] { { ProductionType.RE } }));
		g.addProduction(new Production(ProductionType.RE,
				new ProductionType[][] {
						{ ProductionType.RE, ProductionType.Or,
								ProductionType.T }, { ProductionType.T } }));
		g.addProduction(new Production(ProductionType.T,
				new ProductionType[][] {
						{ ProductionType.T, ProductionType.Cons,
								ProductionType.A }, { ProductionType.A } }));
		g.addProduction(new Production(ProductionType.A,
				new ProductionType[][] {
						{ ProductionType.F, ProductionType.Closure },
						{ ProductionType.F } }));
		g.addProduction(new Production(ProductionType.F,
				new ProductionType[][] {
						{ ProductionType.OpeningParenthesis, ProductionType.RE,
								ProductionType.ClosingParenthesis },
						{ ProductionType.AvailableCharSet } }));
		g.buildLR1Table();

		HashMap<Character, ProductionType> k2t = new HashMap<Character, ProductionType>();
		k2t.put('(', ProductionType.OpeningParenthesis);
		k2t.put(')', ProductionType.ClosingParenthesis);
		k2t.put('+', ProductionType.Cons);
		k2t.put('*', ProductionType.Closure);
		k2t.put('|', ProductionType.Or);
		// k2t.put('a', ProductionType.AvailableCharSet);
		// k2t.put('b', ProductionType.AvailableCharSet);
		// k2t.put('c', ProductionType.AvailableCharSet);

		k2t.put('0', ProductionType.AvailableCharSet);
		k2t.put('1', ProductionType.AvailableCharSet);
		k2t.put('2', ProductionType.AvailableCharSet);
		k2t.put('3', ProductionType.AvailableCharSet);
		k2t.put('4', ProductionType.AvailableCharSet);
		k2t.put('5', ProductionType.AvailableCharSet);
		k2t.put('6', ProductionType.AvailableCharSet);
		k2t.put('7', ProductionType.AvailableCharSet);
		k2t.put('8', ProductionType.AvailableCharSet);
		k2t.put('9', ProductionType.AvailableCharSet);
		k2t.put('.', ProductionType.AvailableCharSet);
		k2t.put('_', ProductionType.EOF);

		List<Character> inputSequence = new ArrayList<Character>();
		//
		// inputSequence.add('a');
		// inputSequence.add('+');
		// inputSequence.add('(');
		// inputSequence.add('b');
		// inputSequence.add('|');
		// inputSequence.add('c');
		// inputSequence.add(')');
		// inputSequence.add('*');
		// inputSequence.add('_');
		//
		// inputSequence.add('(');
		// inputSequence.add(')');
		// inputSequence.add('_');

		String input = "(0|1|2|3|4|5|6|7|8|9)+.+(0|1|2|3|4|5|6|7|8|9)+(0|1|2|3|4|5|6|7|8|9)_";
		// input = "1+.+(2|3)*+4+5_";
		for (char c : input.toCharArray()) {
			inputSequence.add(c);
		}

		Parser<Character> parser = new Parser<Character>(g);
		AST<Character> ast = null;
		try {
			ast = parser.parse(inputSequence, k2t);
		} catch (ASTException e) {
			System.out.println("AST生成错误。");
			System.out.println("位置：" + e.getErrorPosition());
			System.exit(0);
		}

		REAST2NFAConverter<Character> astConverter = new REAST2NFAConverter<Character>();
		NFA<Character> nfa = astConverter.convert(ast);
		if (nfa == null) {
			System.out.println("NFA生成错误。");
		} else {
			System.out.println("NFA生成完成。");
		}

		HashSet<Character> alphabet = new HashSet<Character>();
		// alphabet.add('a');
		// alphabet.add('b');
		// alphabet.add('c');

		alphabet.add('0');
		alphabet.add('1');
		alphabet.add('2');
		alphabet.add('3');
		alphabet.add('4');
		alphabet.add('5');
		alphabet.add('6');
		alphabet.add('7');
		alphabet.add('8');
		alphabet.add('9');
		alphabet.add('.');

		NFA2DFAConverter<Character> nfaConverter = new NFA2DFAConverter<Character>();
		DFA<Character> dfa = nfaConverter.subsetConstruction(alphabet, nfa);
		// dfa.print();
		String ss[] = new String[] { "0.12", "1.232333245", "3.12", "32.12" };
		for (String s : ss) {
			System.out.println("==================");
			System.out.println("匹配：" + s);
			List<Character> i;
			i = new ArrayList<Character>();
			for (char c : s.toCharArray()) {
				i.add(c);
			}
			if (dfa.match(i) == s.length()) {
				System.out.println("匹配成功。");
			} else {
				System.out.print("匹配失败位置：");
				System.out.println(dfa.match(i));
			}
		}
		System.out.println("==================");
	}

	private Map<ProductionType, Production> productions = new HashMap<ProductionType, Production>();

	private Action action = new Action();
	private Goto goto_ = new Goto();

	public Action getAction() {
		return action;
	}

	public Goto get__goto() {
		return goto_;
	}

	public Grammar() {
	}

	public Grammar(List<Production> productions) {
		for (Production production : productions) {
			this.productions.put(production.left, production);
		}
	}

	public void addProduction(Production production) {
		this.productions.put(production.left, production);
	}

	public void buildLR1Table() {
		List<CanonicalCollection> CC = buildCanonicalCollections();
		fillLR1Table(CC, action, goto_);
	}

	private void fillLR1Table(List<CanonicalCollection> CC, Action action,
			Goto goto_) {
		int i = 0;
		int j = 0;
		for (CanonicalCollection cc : CC) {
			for (LR1Item item : cc.getSet().items()) {
				j = CC.indexOf(_goto(cc, item.nextSymbol()));
				if (item.placeholder < item.right.length
						&& ProductionType.isTerminal(item.nextSymbol())
						&& j != -1) {
					action.addRow(i, item.nextSymbol(), ActionType.Shift, j);
				} else if (item.right.length <= item.placeholder
						&& ProductionType.isNotGoal(item.left)) {
					action.addRow(i, item.terminalSymbol, ActionType.Reduce,
							item);
				} else if (ProductionType.isGoal(item.left)
						&& ProductionType.isEOF(item.terminalSymbol)
						&& item.right.length <= item.placeholder) {
					action.addRow(i, ProductionType.EOF, ActionType.Accept);
				}
			}
			for (ProductionType t : ProductionType.nonTerminalSet()) {
				j = CC.indexOf(_goto(cc, t));
				if (j != -1) {
					goto_.addRow(i, t, j);
				}
			}
			++i;
		}
	}

	private List<CanonicalCollection> buildCanonicalCollections() {
		// transitions = new ArrayList<Transition>();
		// initiation
		Production init = this.findProduction(ProductionType.Goal);
		CanonicalCollection cc0 = new CanonicalCollection();
		cc0.addItem(new LR1Item(init.left, init.right[0], 0, ProductionType.EOF));
		cc0 = closure(cc0);

		List<CanonicalCollection> CC = new ArrayList<CanonicalCollection>();
		// while loop
		CC.add(cc0);

		boolean hasAdded = true;
		while (hasAdded) {
			hasAdded = false;
			for (int index = 0; index < CC.size(); ++index) {
				CanonicalCollection cc = CC.get(index);
				if (cc.isMarked()) {
					continue;
				}
				cc.mark();
				for (LR1Item i : cc.getSet().items()) {
					CanonicalCollection temp = _goto(cc, i.nextSymbol());
					int to = indexOf(temp, CC);
					if (to == -1) {
						/**
						 * TODO 这里是对null情况的一次trick，需要查明原因，去掉这句。
						 */
						if (temp.getSet().items().size() == 0) {
							continue;
						}
						CC.add(temp);
						to = CC.size() - 1;
						hasAdded = true;
					}
				}
			}
		}
		return CC;
	}

	private int indexOf(CanonicalCollection temp, List<CanonicalCollection> CC) {
		int idx = 0;
		for (CanonicalCollection cc : CC) {
			if (temp.equals(cc)) {
				return idx;
			}
			idx++;
		}
		return -1;
	}

	private CanonicalCollection closure(CanonicalCollection s) {
		/**
		 * concurrent的问题。
		 */
		while (s.stillChanging()) {
			for (LR1Item item : s.getSet().items().toArray(new LR1Item[0])) {
				if (item.nextSymbolIsNonterminal()) {
					for (ProductionType[] right : findProduction(item
							.nextSymbol()).right) {
						ProductionType[] bs = first(item.nextNextSymbol(),
								item.terminalSymbol);
						for (ProductionType b : bs) {
							s.addItem(new LR1Item(item.nextSymbol(), right, 0,
									b));
						}
					}
				}
			}
		}
		return s;
	}

	// private void printLR1ItemList(CanonicalCollection s) {
	// for (LR1Item item : s.getSet().items()) {
	// System.out.println(item.toString());
	// }
	// }

	private Production findProduction(ProductionType left) {
		return productions.get(left);
	}

	private CanonicalCollection _goto(CanonicalCollection s, ProductionType x) {
		CanonicalCollection moved = new CanonicalCollection();
		for (LR1Item item : s.getSet().items()) {
			if (item.nextSymbolAfterPlaceholderIs(x)) {
				moved.addItem(new LR1Item(item.left, item.right,
						item.placeholder + 1, item.terminalSymbol));
			}
		}
		// System.out.println("Goto before closure:");
		// printLR1ItemList(moved);
		return closure(moved);
	}

	/*
	 * 还是遇到了两个类型不同一的冲突，亟需解决。
	 * 
	 * 冲突出现的原因是：
	 * 
	 * 自己将语法生成式和具体的字符分成了两个系统，但是算法中会遇到两者的同时出现的情况。如何合并两个类型？或者统一？
	 * 
	 * 主要集中与AvailableCharSet这个问题上。
	 * 
	 * 目前的解决方法是，我们整个的都用生成式表示，而不再处理字符系统。
	 */
	private void first(ProductionType nextNextSymbol, List<ProductionType> ret) {
		if (nextNextSymbol == ProductionType.EOF) {
			ret.add(nextNextSymbol);
			return;
		}
		if (ProductionType.isNonterminal(nextNextSymbol)) {
			for (ProductionType[] right : findProduction(nextNextSymbol).right) {
				if (ProductionType.isNonterminal(right[0])) {
					first(right[0], ret);
				} else {
					ret.add(right[0]);
				}
			}

		} else {
			ret.add(nextNextSymbol);
			return;
		}
	}

	private ProductionType[] first(ProductionType nextNextSymbol,
			ProductionType terminalSymbol) {
		if (nextNextSymbol == null) {
			return new ProductionType[] { terminalSymbol };
		}
		List<ProductionType> ret = new LinkedList<ProductionType>();
		first(nextNextSymbol, ret);
		return ret.toArray(new ProductionType[ret.size()]);
	}

}
